#pragma once

#include <cstddef>
#include <deque>

namespace mdtx::online::impl
{
    template <typename T>
    class minmax
    {
    public:
        std::deque<T> mindeq, maxdeq;

        void insert_impl(T x)
        {
            while (!mindeq.empty() && mindeq.back() > x)
                mindeq.pop_back();
            while (!maxdeq.empty() && maxdeq.back() < x)
                maxdeq.pop_back();
            mindeq.push_back(x);
            maxdeq.push_back(x);
        }

        void insert_impl(T high, T low)
        {
            while (!mindeq.empty() && mindeq.back() > low)
                mindeq.pop_back();
            while (!maxdeq.empty() && maxdeq.back() < high)
                maxdeq.pop_back();
            mindeq.push_back(low);
            maxdeq.push_back(high);
        }

        void remove_impl(T old_x)
        {
            if (!mindeq.empty() && mindeq.front() == old_x)
                mindeq.pop_front();
            if (!maxdeq.empty() && maxdeq.front() == old_x)
                maxdeq.pop_front();
        }

        void remove_impl(T high, T low)
        {
            if (!mindeq.empty() && mindeq.front() == low)
                mindeq.pop_front();
            if (!maxdeq.empty() && maxdeq.front() == high)
                maxdeq.pop_front();
        }

        void reset_impl()
        {
            mindeq.clear();
            maxdeq.clear();
        }
    };

    template <typename T>
    class argminmax
    {
    public:
        std::deque<T> mindeq, maxdeq;
        std::deque<ptrdiff_t> minidx, maxidx;

        void insert_impl(T x)
        {
            while (!mindeq.empty() && mindeq.back() > x)
            {
                mindeq.pop_back();
                minidx.pop_back();
            }
            while (!maxdeq.empty() && maxdeq.back() < x)
            {
                maxdeq.pop_back();
                maxidx.pop_back();
            }
            for (auto &i : minidx)
            {
                i += 1;
            }
            for (auto &i : maxidx)
            {
                i += 1;
            }
            mindeq.push_back(x);
            maxdeq.push_back(x);
            minidx.push_back(0);
            maxidx.push_back(0);
        }

        void remove_impl(T x)
        {
            if (!mindeq.empty() && mindeq.front() == x)
            {
                mindeq.pop_front();
                minidx.pop_front();
            }
            if (!maxdeq.empty() && maxdeq.front() == x)
            {
                maxdeq.pop_front();
                maxidx.pop_front();
            }
        }

        void reset_impl()
        {
            mindeq.clear();
            maxdeq.clear();
            minidx.clear();
            maxidx.clear();
        }
    };

    template <typename T, typename C>
    class extrema
    {
    public:
        std::deque<T> deq;

        void insert_impl(T x)
        {
            while (!deq.empty() && C()(x, deq.back()))
            {
                deq.pop_back();
            }
            deq.push_back(x);
        }

        void remove_impl(T x)
        {
            if (!deq.empty() && deq.front() == x)
            {
                deq.pop_front();
            }
        }

        void reset_impl()
        {
            deq.clear();
        }
    };

    template <typename T, typename C>
    class argextrema
    {
    public:
        std::deque<T> deq;
        std::deque<ptrdiff_t> ideq;

        void insert_impl(T x)
        {
            while (!deq.empty() && C()(x, deq.back()))
            {
                deq.pop_back();
                ideq.pop_back();
            }
            for (auto &i : ideq)
            {
                i += 1;
            }
            deq.push_back(x);
            ideq.push_back(0);
        }

        void remove_impl(T x)
        {
            if (!deq.empty() && deq.front() == x)
            {
                deq.pop_front();
                ideq.pop_front();
            }
        }

        void reset_impl()
        {
            deq.clear();
            ideq.clear();
        }
    };
}
